#pragma once
#include<iostream>
#include<vector>
using namespace std;

//链式Hash

//链表点
template <class T>
struct  HashNode
{
	//构造函数
	HashNode(const T&data)
		:data_(data),next_(nullptr)
	{}
	T data_;
	HashNode* next_;
};

//哈希函数的仿函数
template <class K>
class defultfunc
{
public:
	size_t operator()(const K& key)
	{
		return size_t(key);
	}

};
//特化string类的类型
template <>
class defultfunc<string>
{
public:
	size_t operator()(const string& key)
	{
		size_t hashi = 0;
		for (auto c : key)
		{
			hashi = hashi * 131 + c;
		}
		return hashi;
	}
};

//在迭代器类先声明哈希表
template <class K, class T, class hashfunc, class keyoft>
class HashTable;

//迭代器
template <class K,class T,class hashfunc,class keyoft >
class HashIterator
{
	typedef HashNode<T> Node;
	typedef HashIterator<K, T, hashfunc, keyoft> self;
public:
	//默认构造函数
	HashIterator(){}
	HashIterator(Node* node, HashTable<K, T, hashfunc, keyoft>*buket)
		:node_(node),buket_(buket)
	{}

	self& operator++()
	{
		if (node_->next_)
		{
			node_ = node_->next_;
		}
		else
		{
			hashfunc func;
			keyoft kt;
			//寻找下一个不是空的桶
			size_t hashi = func(kt(node_->data_));
			hashi = hashi % (buket_->table_.size());
			hashi++;
			for (;hashi < buket_->table_.size();hashi++)
			{
				if (buket_->table_[hashi])
				{
					node_ = buket_->table_[hashi];
					break;
				}

			}
			//如果后续所有的桶都是空，那么就用nullptr作为end指针
			if (hashi == buket_->table_.size())
			{
				node_ = nullptr;
			}
		}
		return *this;
	}
	T& operator*()
	{
		return node_->data_;
	}
	T* operator->()
	{
		return &node_->data_;
	}
	bool operator!=(const self& s)const
	{
		return node_ != s.node_;
	}
	bool operator==(const self& s)const
	{
		return node_ == s.node_;
	}
	HashTable<K, T, hashfunc, keyoft>* buket_;
	Node* node_;
};

template <class K, class T,class hashfunc,class keyoft>
class HashTable
{

public:
	typedef HashNode<T> Node;
	//将迭代器设置为哈希表的友元
	//这样迭代器就可以访问哈希表中的私有类
	template <class K, class T, class hashfunc, class keyoft >
	friend class HashIterator;
	//迭代器
	typedef HashIterator<K, T, hashfunc, keyoft> iterator;
	//构造函数
	HashTable()
	{}
	//析构函数
	~HashTable()
	{
		for (size_t i = 0;i < table_.size();i++)
		{
			Node* cur = table_[i];
			while (cur)
			{
				Node* next = cur->next_;
				delete cur;
				cur =next;
			}
			table_[i] = nullptr;
		}
	}
	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		static const size_t primeList[PRIMECOUNT] =
		{
			53ul, 97ul, 193ul, 389ul, 769ul,
			1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
			49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
			1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
			50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
			1610612741ul, 3221225473ul, 4294967291ul
		};

		// 获取比prime大那一个素数
		size_t i = 0;
		for (; i < PRIMECOUNT; ++i)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		return primeList[i];
	}
	iterator end()
	{
		return iterator(nullptr,this);
	}
	iterator begin()
	{
		for (size_t i = 0;i < table_.size();i++)
		{
			Node* cur = table_[i];
			if (cur)
			{
				return iterator(cur,this);
			}
		}
		return end();
	}
	pair<iterator, bool> insert(const T& data)
	{
		hashfunc hf;
		keyoft kot;

		iterator pos = find(kot(data));
		if (pos != end())
		{
			return make_pair(pos, false);
		}

		// 负载因子 == 1 扩容
		if (table_.size()== n_)
		{
			//size_t newSize = _tables.size() == 0 ? 11 : _tables.size() * 2;
			size_t newSize = GetNextPrime(table_.size());
			if (newSize != table_.size())
			{
				vector<Node*> newTable;
				newTable.resize(newSize, nullptr);
				for (size_t i = 0; i < table_.size(); ++i)
				{
					Node* cur = table_[i];
					while (cur)
					{
						Node* next = cur->next_;

						size_t hashi = hf(kot(cur->data_)) % newSize;
						cur->next_ = newTable[hashi];
						newTable[hashi] = cur;

						cur = next;
					}

					table_[i] = nullptr;
				}

				newTable.swap(table_);
			}
		}

		size_t hashi = hf(kot(data));
		hashi %=table_.size();

		// 头插到对应的桶即可
		Node* newnode = new Node(data);
		newnode->next_ =table_[hashi];
		table_[hashi] = newnode;

		++n_;

		return make_pair(iterator(newnode, this), false);;
	}


	//查找函数
	iterator find(const K& key)
	{
		if (table_.size()== 0)
		{
			return iterator(nullptr, this);
		}
		keyoft kot;
		hashfunc hf;
		size_t hashi = hf(key);
		//size_t hashi = HashFunc()(key);

		hashi %= table_.size();
		Node* cur =table_[hashi];
		while (cur)
		{
			if (kot(cur->data_) == key)
			{
				return iterator(cur, this);
			}

			cur = cur->next_;
		}

		return iterator(nullptr, this);
	}
	bool erase(const K&key)
	{
		if (table_.size() == 0)
		{
			return false;
		}
		hashfunc func;
		keyoft kt;
		size_t hashi = func(kt(key));
		hashi %= table_.size();
		Node* cur = table_[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (kt(cur->data_) == key)
			{
				if (prev == nullptr)
				{
					table_[hashi] = cur->next_;
				}
				else
				{
					prev->next_ = cur->next_;
				}
				delete cur;
				return true;
			}
			prev = cur;
			cur = cur->next_;
		}
		return false;
	}
public:
	vector<Node*> table_;
	size_t n_=0;
};